{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sort Integers by The Number of 1 Bits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sortByBits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #根据数字二进制下 1 的数目排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>arr</code>&nbsp;。请你将数组中的元素按照其二进制表示中数字 <strong>1</strong> 的数目升序排序。</p>\n",
    "\n",
    "<p>如果存在多个数字二进制中&nbsp;<strong>1</strong>&nbsp;的数目相同，则必须将它们按照数值大小升序排列。</p>\n",
    "\n",
    "<p>请你返回排序后的数组。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [0,1,2,3,4,5,6,7,8]\n",
    "<strong>输出：</strong>[0,1,2,4,8,3,5,6,7]\n",
    "<strong>解释：</strong>[0] 是唯一一个有 0 个 1 的数。\n",
    "[1,2,4,8] 都有 1 个 1 。\n",
    "[3,5,6] 有 2 个 1 。\n",
    "[7] 有 3 个 1 。\n",
    "按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [1024,512,256,128,64,32,16,8,4,2,1]\n",
    "<strong>输出：</strong>[1,2,4,8,16,32,64,128,256,512,1024]\n",
    "<strong>解释：</strong>数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [10000,10000]\n",
    "<strong>输出：</strong>[10000,10000]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [2,3,5,7,11,13,17,19]\n",
    "<strong>输出：</strong>[2,3,5,17,7,11,13,19]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>arr = [10,100,1000,10000]\n",
    "<strong>输出：</strong>[10,100,10000,1000]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 500</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sort-integers-by-the-number-of-1-bits](https://leetcode.cn/problems/sort-integers-by-the-number-of-1-bits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sort-integers-by-the-number-of-1-bits](https://leetcode.cn/problems/sort-integers-by-the-number-of-1-bits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2,3,4,5,6,7,8]', '[1024,512,256,128,64,32,16,8,4,2,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        def custom(num):\n",
    "            bit_cnt = bin(num).count('1')\n",
    "            return (bit_cnt, num)\n",
    "        arr.sort(key=custom)\n",
    "        return arr\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "         return sorted(arr, key=lambda x: (bin(x).count('1'), x))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "def cmpx(a, b):\n",
    "    _l1 = sum([1 for i in bin(a) if i == '1'])\n",
    "    _l2 = sum([1 for i in bin(b) if i == '1'])\n",
    "\n",
    "    if _l1 > _l2:\n",
    "        return 1\n",
    "\n",
    "    if _l1 == _l2:\n",
    "        if a > b:\n",
    "            return 1\n",
    "        elif a == b:\n",
    "            return 0\n",
    "        else:\n",
    "            return -1\n",
    "    \n",
    "    return -1\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        return sorted(arr, key=functools.cmp_to_key(cmpx))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr):\n",
    "        arr.sort()\n",
    "        arr = [(x, bin(x)[2:].count('1')) for x in arr]\n",
    "        arr.sort(key = lambda x : x[1])\n",
    "        return [x[0] for x in arr]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        bin_list = list()\n",
    "        for i in range(len(arr)):\n",
    "            x = bin(arr[i]).replace('0b','')\n",
    "            bin_list.append(x)\n",
    "        for i in range(0,len(bin_list)-1):\n",
    "            for j in range(i+1,len(bin_list)):\n",
    "                if bin_list[i].count(\"1\") > bin_list[j].count(\"1\"):\n",
    "                    mid = bin_list[j]\n",
    "                    bin_list[j] = bin_list[i]\n",
    "                    bin_list[i] = mid\n",
    "\n",
    "                    medium = arr[j]\n",
    "                    arr[j] = arr[i]\n",
    "                    arr[i] = medium\n",
    "                if bin_list[i].count(\"1\") == bin_list[j].count(\"1\") and arr[i] > arr[j]:\n",
    "                    mid1 = bin_list[j]\n",
    "                    bin_list[j] = bin_list[i]\n",
    "                    bin_list[i] = mid1\n",
    "\n",
    "                    medium1 = arr[j]\n",
    "                    arr[j] = arr[i]\n",
    "                    arr[i] = medium1\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        oneNum = []\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            oneNum.append(bin(arr[i])[2:].count('1'))\n",
    "            # 要用最笨的方法啊\n",
    "            # 去重\n",
    "        oneNum_only = list(set(oneNum))\n",
    "        res = []\n",
    "        for idx in oneNum_only:\n",
    "            temp = []\n",
    "            for i in range(len(oneNum)):\n",
    "                if oneNum[i] == idx:\n",
    "                    temp.append(arr[i])\n",
    "            temp.sort()\n",
    "            res.append(temp.copy())\n",
    "        theRes = []\n",
    "        for item in res:\n",
    "            for idx in range(len(item)):\n",
    "                theRes.append(item[idx])\n",
    "        return theRes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        dic = {}\n",
    "        lisSort = []\n",
    "        for i in arr:\n",
    "            account = bin(i).count('1')\n",
    "            if account not in dic.keys():\n",
    "                dic[account] = []\n",
    "                dic[account].append(i)\n",
    "            else:\n",
    "                dic[account].append(i)\n",
    "        lis = [i for i in dic.keys()]\n",
    "        lis.sort()\n",
    "        for i in lis:\n",
    "            values = dic[i]\n",
    "            values.sort()\n",
    "            lisSort += values\n",
    "        return lisSort\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        count = [0 for _ in range(10001)]\n",
    "        for i in range(1, 10001):\n",
    "            count[i] = count[i>>1] + int(i&1)\n",
    "        \n",
    "        return sorted(arr, key=lambda x: (count[x], x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        hashmap = {}\n",
    "\n",
    "        def getOneCount(num):\n",
    "            res = 0\n",
    "            while num:\n",
    "                res += 1\n",
    "                num &= num - 1\n",
    "            return res\n",
    "\n",
    "        def quickSort(arr, left, right):\n",
    "            if left >= right:\n",
    "                return\n",
    "            partition_index = partition(arr, left, right)\n",
    "            quickSort(arr, left, partition_index - 1)\n",
    "            quickSort(arr, partition_index + 1, right)\n",
    "    \n",
    "        def partition(arr, left, right):\n",
    "            pivot = left\n",
    "            index = pivot + 1\n",
    "            for i in range(left + 1, right + 1):\n",
    "                if hashmap[arr[i]] < hashmap[arr[pivot]]:\n",
    "                    arr[i], arr[index] = arr[index], arr[i]\n",
    "                    index += 1\n",
    "                elif hashmap[arr[i]] == hashmap[arr[pivot]]:\n",
    "                    if arr[i] < arr[pivot]:\n",
    "                        arr[i], arr[index] = arr[index], arr[i]\n",
    "                        index += 1\n",
    "            arr[pivot], arr[index - 1] = arr[index - 1], arr[pivot]\n",
    "            return index - 1\n",
    "\n",
    "        for num in arr:\n",
    "            hashmap[num] = getOneCount(num)\n",
    "        quickSort(arr, 0, len(arr) - 1)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        hashmap = {}\n",
    "\n",
    "        def getOneCount(num):\n",
    "            res = 0\n",
    "            while num:\n",
    "                res += 1\n",
    "                num &= num - 1\n",
    "            return res\n",
    "\n",
    "        def quickSort(arr, left, right):\n",
    "            if left >= right:\n",
    "                return\n",
    "            partition_index = partition(arr, left, right)\n",
    "            quickSort(arr, left, partition_index - 1)\n",
    "            quickSort(arr, partition_index + 1, right)\n",
    "    \n",
    "        def partition(arr, left, right):\n",
    "            pivot = left\n",
    "            index = pivot + 1\n",
    "            for i in range(left + 1, right + 1):\n",
    "                if hashmap[arr[i]] < hashmap[arr[pivot]]:\n",
    "                    arr[i], arr[index] = arr[index], arr[i]\n",
    "                    index += 1\n",
    "                elif hashmap[arr[i]] == hashmap[arr[pivot]]:\n",
    "                    if arr[i] < arr[pivot]:\n",
    "                        arr[i], arr[index] = arr[index], arr[i]\n",
    "                        index += 1\n",
    "            arr[pivot], arr[index - 1] = arr[index - 1], arr[pivot]\n",
    "            return index - 1\n",
    "\n",
    "        for num in arr:\n",
    "            hashmap[num] = getOneCount(num)\n",
    "        quickSort(arr, 0, len(arr) - 1)\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        @lru_cache(None)\n",
    "        def count(e):\n",
    "            return bin(e).count(\"1\")\n",
    "\n",
    "        arr.sort(key=lambda e: (count(e), e))\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        return sorted(arr,key=lambda x: (bin(x).count(\"1\"),x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        arr.sort(key=lambda n:(self.getBits(n),n))\n",
    "        return arr\n",
    "    \n",
    "    def getBits(self, n):\n",
    "        count = 0\n",
    "        while n:\n",
    "            n &= n-1\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        def count_binary_1(num):\n",
    "            ans = 0\n",
    "            while num:\n",
    "                ans += 1\n",
    "                num &= (num-1)\n",
    "            return ans\n",
    "        count_dict = {}\n",
    "        for num in arr:\n",
    "            temp = count_binary_1(num)\n",
    "            if temp in count_dict:\n",
    "                count_dict[temp].append(num)\n",
    "            else:\n",
    "                count_dict[temp] = [num]\n",
    "        res_list = sorted(count_dict.items())\n",
    "        res = []\n",
    "        for _, num in res_list:\n",
    "            res += sorted(num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        for i in arr:\n",
    "            res.append([i, bin(i)[2:]])\n",
    " \n",
    "        res = sorted(res, key = lambda x : [x[1].count(\"1\"), int(x[0])])\n",
    "        print(res)\n",
    "        ans = []\n",
    "        for i in res:\n",
    "            ans.append(int(i[0]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        def bin_car(num):\n",
    "            count = 0\n",
    "            while num != 0:\n",
    "                if num % 2 == 1:\n",
    "                    count += 1\n",
    "                num = num // 2\n",
    "            return count\n",
    "        def compare(a, b):\n",
    "            bin_a, bin_b = bin_car(a), bin_car(b)\n",
    "            if bin_a < bin_b:\n",
    "                return 0\n",
    "            if bin_a > bin_b:\n",
    "                return 1\n",
    "            return 0 if a <= b else 1\n",
    "        def MergeSort(start, end):\n",
    "            if start == end:\n",
    "                return [arr[start]]\n",
    "            if start < end:\n",
    "                mid = (start + end) // 2\n",
    "                L1 = MergeSort(start, mid)\n",
    "                L2 = MergeSort(mid+1, end)\n",
    "                L = []\n",
    "                while L1 and L2:\n",
    "                    if compare(L1[0], L2[0]):\n",
    "                        L.append(L2[0])\n",
    "                        del L2[0]\n",
    "                    else:\n",
    "                        L.append(L1[0])\n",
    "                        del L1[0]\n",
    "                if L1:\n",
    "                    return L + L1\n",
    "                return L + L2\n",
    "        return MergeSort(0, len(arr)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        return sorted(arr, key = lambda x:(x.bit_count(), x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        for i in range(1, n):\n",
    "            for j in range(n - i):\n",
    "                if arr[j].bit_count() > arr[j + 1].bit_count():\n",
    "                    arr[j], arr[j + 1] = arr[j + 1], arr[j]\n",
    "                elif arr[j].bit_count() == arr[j + 1].bit_count() and arr[j] > arr[j + 1]:\n",
    "                    arr[j], arr[j + 1] = arr[j + 1], arr[j]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sortByBits(self, arr: List[int]) -> List[int]:\n",
    "        cnt = collections.defaultdict(list)\n",
    "        for num in arr:\n",
    "            c = 0\n",
    "            for i in str(bin(num)):\n",
    "                if i == '1':\n",
    "                    c += 1\n",
    "            cnt[c].append(num)\n",
    "        \n",
    "        keys = sorted(cnt.keys())\n",
    "        ans = []\n",
    "        for key in keys:\n",
    "            ans += sorted(cnt[key])\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
